package com.my.learn.exercise.data.struct.leetcode.difficult;
/*
 * 创建人：baimiao
 * 创建时间：2024/3/12 13:50
 *

719. 找出第 K 小的数对距离
困难
相关标签
相关企业
提示
数对 (a,b) 由整数 a 和 b 组成，其数对距离定义为 a 和 b 的绝对差值。

给你一个整数数组 nums 和一个整数 k ，数对由 nums[i] 和 nums[j] 组成且满足 0 <= i < j < nums.length 。返回 所有数对距离中 第 k 小的数对距离。



示例 1：

输入：nums = [1,3,1], k = 1
输出：0
解释：数对和对应的距离如下：
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
距离第 1 小的数对是 (1,1) ，距离为 0 。
示例 2：

输入：nums = [1,1,1], k = 2
输出：0
示例 3：

输入：nums = [1,6,1], k = 3
输出：5
 *
 */

import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

public class SmallestDistancePair {
    public static void main(String[] args) {
        int k = 4;
//        int[] nums = {197180,567032,701885,294688,49821,319144,793670,35956,30654,462823,954237,828852,85004,156833,193021,362217,197278,327502,82298,521188,951833,265111,760577,510602,668226,3307,908042,352949,860824,129537,908611,25249,417829,291862,465673,534186,369397,683232,173430,18207,82787,876718,391394,475845,722608,190000,969787,233166,662525,607653,200810,935100,640383,693229,625474,122557,533527,260952,707482,765465,845266,157430,435025,90838,620046,538885,587099,596938,443819,627769,682479,56604,286713,267635,810558,457445,369187,956105,591738,68417,48665,381853,999042,500394,630032,323115,736066,650057,579736,492572,594889,681727,648476,489128,546548,374299,783065,38284,13220,596704,598511,384239,638410,55052,936220,399790,922645,771376,626086,623725,130425,34870,312207,925749,660887,584385,191057,200707,583676,297674,117068,113528,42937,94302,896727,371017,964230,600323,856003,671048,276365,771512,3835,306347,525872,295193,529473,963721,601928,136931,129565,459260,140827,904512,987024,436624,489672,82935,960898,859620,843811,32944,828990,201443,937507,585595,70375,448112,933974,569408,236339,971838,379143,498500,546479,56608,610197,117083,470717,78277,439988,425379,615416,514394,296548,271413,76011,978081,603937,393688,273149,81525,880102,364966,364381,272250,317743,552991,195896,918495,869437,638686,466379,537575,803871,890732,747277,626373,201056,341977,189149,259704,36461,434740,613412,21800,978801,762134,307758,814170,195211,658684,989269,93562,580701,407882,140920,599676,551519,772480,922489,783429,577383,876213,150333,95805,943354,1815,773057,936455,557840,573860,696063,240428,132502,906863,110557,970566,262927,322797,238051,775953,691630,221805,679158,229601,387288,549635,147070,165593,742521,723065,476921,22860,137692,621763,110984,818869,9460,636648,117176,631137,664359,279407,12375,260199,462089,862555,828749,902128,560565,458550,118747,197335,535240,360820,679017,643935,374215,714356,896603,61759,7125,691590,22273,774046,392237,90279,659709,891104,484757,281464,886138,17869,47516,121401,136681,531063,301053,95468,645767,154683,861940,981055,772378,458822,510786,667702,897655,93896,154311,979714,242923,321638,896685,282348,606268,905787,418330,126778,150270,326502,680627,394,622114,979631,974401,387808,236432,143990,551797,979906,477188,703793,129928,670854,426538,318678,228140,971328,998219,650386,508009,64167,727696,885179,730394,401257,159439,927117,281326,632924,414042,563269,35018,532472,97627,155052,888771,604117,390350,971798,849885,829612,17184,838357,860317,975320,494257,482182,175805,265029,732863,81541,475487,345034,591676,788846,788335,434100,512869,142266,276883,159383,543296,645572,844360,544748,530566,441608,626208,595451,788244,38129,965907,6475,559988,278906,903361,411616,606767,298266,280090,331740,543601,4289,990479,131651,510330,298111,445022,692353,538452,678540,276344,416483,771474,242780,135645,796355,409593,870923,109422,632455,872740,512578,325021,684730,572102,90258,580077,179525,298448,333323,917066,578630,701530,568637,193656,863330,899504,265380,536558,59592,728252,605281,885512,984888,558937,873510,586455,896449,547050,845741,913377,290062,2595,771493,446140,423256,910729,366719,559481,725190,13466,557895,21697,302767,984904,734345,284393,8670,740881,351858,989249,130194,944115,696781,162129,771026,601439,163705,950662,859846,27005,899816,435139,247523,343790,97381,401373,914843,426395,952446,318514,429013,706227,448630,236511,201989,162606,898963,412648,932782,431170,903346,43288,317790,692510,763717,270754,478441,883868,287135,940846,97256,330719,752417,370197,264251,603678,516620,193141,136381,788313,675601,573069,891293,822852,159055,461520,82631,507049,661084,567251,268684,720805,668686,529552,372260,249306,957404,643578,923664,635606,899776,917487,41512,392265,291646,887338,23163,153985,202402,152565,363200,928030,164426,487735,962176,560435,221493,889385,980431,846174,843827,431929,797050,4130,208076,728367,793299,797987,575597,86975,318983,524654,945873,635639,593132,345910,910226,805703,938781,575958,606967,315567,722457,856262,620516,548556,421284,32866,477522,356809,737976,585153,695598,388779,857475,26292,605658,295266,778950,611057,321321,228628,526179,927480,865843,765893,233688,315017,694910,257967,964064,544128,606643,135407,717710,515726,641216,953480,571063,657188,65344,814170,347945,819442,287626,633939,299528,705240,495224,281339,555593,911630,765400,451430,62960,971989,620830,250028,415037,348769,738027,750184,362865,396049,893686,782157,161747,172721,138915,521915,504092,405586,662543,471933,362044,548218,274433,587072,543147,672696,993553,936389,237981,605162,556298,799299,473530,678492,560934,583177,763173,714624,278096,816224,494356,798547,258655,842530,619873,862897,245485,243523,260043,797014,990717,707342,944342,566721,197076,736850,36777,336616,961796,366950,537168,422914,434049,1442,520290,138071,583219,484161,722352,402343,972482,687957,570516,177653,195761,939239,963537,521486,357704,106892,438854,532776,368633,360796,494022,102371,671304,17947,238659,416667,168943,280214,53180,709044,44094,959832,129038,771431,942598,49135,562780,734285,126809,514109,217519,158822,96225,795261,659474,869970,122026,557963,29702,568768,993741,255043,402084,9948,910982,552521,266726,503273,487330,109913,697890,819901,410910,556547,705826,169242,754342,643277,291015,402205,14542,124687,708094,174311,944730,540390,74269,442421,992878,466858,767999,368801,520964,622857,877932,454307,59819,769142,94812,351694,194701,617641,611086,435933,438039,379440,216080,302644,565559,276803,247497,624969,25134,569641,645354,246817,882209,492821,567117,373456,326874,804688,747092,827878,365412,518317,255460,784764,18319,761054,536202,814815,787045,241070,185778,737519,770870,177149,572205,990096,938570,141722,87562,916611,212228,419607,196269,810309,137899,260418,599992,168151,790397,938582,32951,822993,730875,785237,762741,972643,574948,666462,654687,316075,499059,185381,40791,657698,993842,876982,629090,888648,115628,505570,547939,754928,856966,171158,243635,297309,444684,915873,506139,65457,182836,910261,285579,541492,720362,90168,906013,240911,984588,339175,274630,830227,540225,773311,678958,833766,739114,138863,643530,346066,936330,30325,912691,246626,961428,245578,255104,979704,248171,653069,42054,493713,73880,989630,26066,360072,217194,471208,530511,294235,979067,77774,876554,531491,531929,861336,253883,868970,245116,993151,518046,997241,595451,411888,371395,368434,208904,463918,640801,412051,246548,121914,845571,729834,96644,292060,922913,440516,855199,763623,2834,337755,296897,914276,841187,464834,801906,804831,442523,232495,699364,912716,206965,834329,439203,447070,560044,303228,728308,58709,189382,547193,815611,707779,233235,583605,761298,122313,633709,392716,84716,30564,844372,806994,330500,155800,177840,707376,901555,813587,605694,524233,406760,7613,447052,105177,816752,948700,564277,408249,464174,514329,739975,589676,152165,708938,769700,988758,144764,938811,429143,964066,802117,514990,142507,655498,660259,79727,43326,787556,293121,880253,323632,665689,579346,747669,923670,439130,24495,195570,486810,454711,559970,658784,330733,851052,394267,296669,830328,448248,958380,475200,976363,617718,561004,978699,977703,884150,747266,413622,41599,47052,500278,529384,916731,516235,381877,363127,494730,492683,813876,268904,158255,636861,186156,361660,21557,498565,298022,770405,834343,99885,184194,807717,45427,777067,427623,438643,932434,804568,324789,726992,423130,771540,260512,612068,627285,837393,58997,342724,976482,575930,8867,301046,851918,75024,964463,82488,431774,533362,150838,309271,79014,481765,881159,645353,939537,271051,834105,66965,288483,961641,701880,761472,250899,906914,762772,764645,415599,922715,440830,866787,586557,989973,542631,949276,214171,666047,560663,217817,851017,958413,965335,800209,873515,572566,356241,150921,791920,139845,569774,32065,78047,860517,196276,187443,128562,133682,151674,207978,489975,151454,808127,113620,955288,657820,545580,805746,486414,423127,137311,691099,757170,563178,549713,444979,27099,543962,899319,94763,716154,397716,294219,27748,231604,585419,707587,215600,813601,855956,610743,383755,25112,800671,223594,809757,982545,731585,104923,380043,90668,691949,935321,185917,471685,268957,815173,925878,731903,171280,622105,582672,428100,363410,529336,207875,499781,360509,49498,499774,311021,945282,483201,994527,606152,602501,486726,407084,488849,176121,699060,779425,543589,864540,38408,396423,549453,944094,573443,365420,706941,372792,115072,825835,424338,86166,276640,755658,437577,699030,987017,372965,820541,696245,125464,975310,722544,148149,627441,142933,537474,876461,707447,244048,791845,904507,558954,333536,365468,530203,796905,55498,258553,102893,422976,432190,227076,392889,679800,319156,393406,479004,768337,765995,843998,54491,179250,839033,572420,94613,718463,417703,45467,126304,936693,391578,693297,437036,391905,802332,756145,529841,943609,756258,914098,506736,125337,807596,109416,492293,563341,770274,989862,145705,365524,309275,997021,333032,705714,8954,25138,227866,944696,665664,772860,812837,474026,731129,875920,898776,103210,256965,169501,653111,192266,567681,40311,974575,573241,432818,809247,24321,107816,778615,531109,536285,82416,359723,656922,913249,57304,558529,908219,60390,402343,982695,32981,946606,966295,844320,704478,639714,251699,467431,140366,190446,971551,35940,29988,568025,388157,593820,856662,240874,239601,137385,939713,468473,412571,929177,851960,17084,681517,350622,941710,154127,240923,593910,491547,829259,506098,838780,179240,542284,196754,493190,980305,611074,799220,268779,209118,366446,925055,347413,640269,861330,535487,868203,574357,287504,854196,57515,889212,897774,172859,510005,80366,593042,703196,259776,413961,289446,185127,508919,694452,902407,373037,325073,61352,323584,440512,910215,26904,691804,665458,364913,664904,950599,577159,825577,519443,113249,407742,371124,634982,882451,654245,619070,635692,46239,869116,670389,1178,739047,116167,601107,539492,985452,364151,351134,794692,440037,214915,1008,441540,360834,208547,195723,663975,930361,814908,429207,365901,166420,16347,22444,504243,543754,473508,112128,745908,701947,940495,975090,611724,716273,841772,467480,478866,12502,612038,323016,456645,866878,440364,884525,527988,499317,740370,352037,470443,487362,369199,92179,317273,254299,354914,115031,635139,706136,116984,438009,674234,391688,705838,365495,702295,335848,257630,437409,165324,316903,716769,834429,738506,230127,506257,819441,713117,115614,334009,65575,561109,984858,54674,236133,763868,478983,452755,179204,69600,104731,81161,332687,3372,851334,416088,307383,466042,593339,811825,238319,323662,715685,133692,895037,540699,977545,177135,188844,119812,37389,589374,281603,917,224623,712432,118722,746748,264988,825257,634379,771020,357686,380583,315795,943412,400260,592507,494387,579488,448088,181941,949371,909421,8612,486808,931308,913636,495934,603,558165,47515,720721,620780,936662,803130,160556,868039,72573,3867,669452,115972,978387,307995,704740,361456,925026,965123,297222,966715,241999,552202,672857,303851,942098,16325,492994,598936,353336,459357,723540,783227,956263,411650,934775,203175,994379,13551,140654,342221,372036,195501,317154,647446,791153,980800,273155,839642,418881,965073,762273,547051,785092,190000,131861,743947,401364,763628,305518,923697,465951,631582,328784,665284,151487,679969,41349,852916,749702,80142,518247,991487,993676,52519,878154,529954,2349,213444,19676,860405,331753,455367,185432,595363,440451,727791,124949,89259,306262,276698,229646,220673,942485,161640,742937,924960,310775,249847,954443,473570,70204,194252,228286,672606,296969,562994,588384,821765,579077,364393,56025,692814,819218,164959,962813,8351,949375,917609,508695,213765,61566,291726,490425,568155,368856,36342,418992,8653,567270,310612,307726,484530,397339,313111,413243,540835,581352,47534,622988,467552,546798,16053,780240,477922,128823,886634,530119,556236,244693,221555,621597,692058,810802,554585,986761,125677,952795,680852,278153,164596,519072,259485,8804,69837,865984,877882,878137,116717,928987,885740,745956,54868,86922,190338,735914,209441,442294,644449,150431,975710,524794,41073,326949,117506,325312,464414,326643,357374,474892,481412,238754,949206,123977,573472,592813,152273,169779,305259,427149,676521,368013,124312,997304,997827,378218,522239,505109,662680,515729,737769,831515,112856,215620,208078,167428,977313,782128,909695,7082,108416,185576,155533,171202,864991,131768,944446,821672,510622,979791,953772,333412,900565,352841,847747,837781,39001,164900,299419,881986,127894,178796,777157,333262,585220,313656,273073,96706,616344,271251,815390,273887,431689,758389,1769,619253,248649,981165,606416,181888,880655,200350,965013,270487,305814,27178,124969,452599,512991,305460,835077,83372,755787,485919,42276,527611,544853,489394,573799,48484,492550,960760,214242,451423,987915,463234,773220,145810,638649,540532,441259,382719,698005,317977,976626,592199,788830,987770,291623,739529,660345,938667,67594,25460,439829,196445,192961,404486,703532,957522,864329,488212,104980,478587,269007,88741,416617,955007,202587,874526,360666,863798,368014,268746,945029,927135,333984,502225,529971,337973,152269,74447,985853,425638,191581,415499,268373,739055,762391,71525,245774,134864,51242,280010,588893,341402,226874,701916,778215,266157,437762,543835,914133,533844,740050,874357,242473,385010,706940,556090,128518,739448,792895,895569,976074,897992,600164,654374,197781,283770,814498,648582,100034,591767,579438,843759,60640,256990,646960,40462,160059,183756,281191,932120,903371,73298,414671,763831,4713,77833,437042,834233,870451,325289,204468,885564,548923,309040,404198,410419,388402,274697,143017,351474,71755,966297,257641,66442,2630,977980,442474,847244,500339,798800,854673,535288,98062,272948,934722,475362,895652,937253,673301,936654,403495,644050,748806,138989,848843,650352,730081,53707,291546,872326,889821,599917,871995,88756,969786,862807,80883,364533,111670,310534,271167,536529,598944,692888,525646,99803,488145,17013,762177,34358,283391,659994,33071,369860,512381,647203,391695,921982,889580,38283,295605,968947,239866,82741,826458,205194,273055,780039,253968,499349,532470,199402,5825,211114,530513,109825,901070,462030,407741,255242,78669,108340,337679,960804,356226,701677,332062,902243,485516,220568,104886,895089,719513,931161,95887,98592,702289,717281,416464,182518,155812,890227,157096,499833,866887,701155,757119,23522,300827,768752,443560,616101,385845,306332,957064,832948,610586,858154,448586,157021,97414,842834,352967,316046,764931,44685,991278,846098,72829,864474,545917,519479,847624,964604,936514,142804,249078,29914,494591,120209,473143,694904,887767,315377,910788,622688,181443,899656,297422,262186,504640,813323,552631,280292,506617,738345,133984,249257,648504,542019,385922,616068,373741,226613,890606,869983,483492,859105,47998,550111,500819,92154,659468,360847,694965,822391,603091,463675,538000,762227,472477,734103,527216,156169,399648,631991,83781,395642,587395,307752,70495,761355,834751,497051,424449,106535,615874,158979,666047,429743,2209,619175,659602,740768,889559,680516,823146,638694,515470,79024,102759,176084,720381,450342,770893,622234,25283,506103,975958,717071,749893,390081,911194,172219,999338,637643,928348,207881,68196,772819,942140,744056,616318,683358,517188,525373,878671,973586,732532,893521,255025,68169,764453,748405,48303,360784,451874,994001,759875,396761,356730,564398,903411,42965,358941,637343,537633,241137,194807,70408,670985,662013,845816,105390,657202,545005,895523,63973,959933,701549,530947,61626,157857,786259,206568,534641,776564,143916,466844,778727,618490,431340,791300,739399,569880,360808,994730,41591,947986,133142,505978,136408,499730,964568,819852,115609,769678,612624,455661,406322,455160,819683,386511,693523,489411,994884,949986,600856,639650,440754,100545,764923,898797,851607,562669,449219,658057,696734,892438,302277,729194,784936,268843,770878,682823,327371,230771,821880,75821,132518,718494,765710,394926,692127,973865,979682,112981,491766,49275,918115,481580,932591,877940,996231,661541,441301,937251,115050,641195,942038,662056,922349,627868,794458,778082,361731,18358,404603,2727,969412,339685,894690,793717,706702,667045,508135,410742,21537,438235,414094,694580,360678,489843,658522,453121,529485,784009,29377,102280,851573,476831,702553,41743,880047,735385,551456,152528,585954,895331,984138,962059,405225,724580,142714,690646,20115,140989,743974,278050,647388,833949,684397,758971,509038,736987,420011,557962,33137,243121,170820,188702,568675,54575,105544,689132,560486,567574,597581,564874,942583,748941,802382,819886,777585,833901,293490,900820,901869,228547,963740,629782,985992,620677,659612,439414,45229,741885,887782,331136,761217,241826,739564,526878,312079,226230,821074,341684,765224,655355,999840,975567,322683,667089,712679,499176,34697,357264,721758,151288,278809,829840,432941,375315,914121,794842,460921,890478,965935,585823,500812,993535,155139,509996,506062,359360,817254,102471,529888,970569,576046,39787,10492,594685,53714,970688,102564,83315,186638,101817,567768,849518,76383,311520,290414,908524,656338,770561,555909,611049,371890,570454,217717,329081,178228,879618,989074,231432,869270,689799,360433,116990,896363,625208,215443,68743,363203,653474,877974,222737,625581,875969,966998,130464,824042,33405,727716,525627,648883,261367,725282,745218,864457,880251,530646,903051,344774,728926,271763,290178,720782,505154,539993,322317,169586,750221,720249,653702,50862,179595,92833,426010,995395,163610,9545,80517,511453,76585,594693,369616,445401,433151,202147,879875,605038,911648,315265,284449,70590,564182,753395,133099,92640,472766,802533,94066,93050,862433,128375,12447,24942,199250,421960,625440,610620,197443,419031,722414,100456,485703,419838,956023,958882,841686,435205,947425,989969,958384,296656,597648,678992,178851,320241,866796,966262,715427,247065,494294,769285,318264,780857,456222,82945,125743,953875,708311,941798,211162,413713,653838,574669,813174,896404,777940,358445,710338,442031,583926,994642,382324,241767,429278,161804,553441,680428,915472,354428,330251,949116,92777,993738,411401,393817,842710,264605,423510,469547,634759,160464,197302,421605,698439,771471,365743,147610,911013,893992,670597,795217,607441,396327,65531,145770,70388,720735,328846,508932,11917,218722,248336,175998,831299,169520,814346,429929,881782,704112,954799,784527,552015,585158,309869,416881,580984,734248,428180,641300,740628,871659,584917,731646,828436,15341,408594,915765,147299,235082,754033,687468,378845,655030,3197,747155,106008,963554,974050,492958,141620,693268,369145,500573,164350,813422,304084,839721,841855,813789,472028,462608,348137,210911,383089,249182,773567,699676,864279,580267,943127,491580,192492,591124,699066,745894,141624,626763,960822,699830,262481,266514,514589,547672,387757,806089,536772,755456,461998,254781,966995,889482,441408,58601,343863,655552,99128,337901,502691,634500,869585,684080,53631,6494,338840,364471,511628,793599,694384,932576,881832,913903,543806,628236,318960,162877,360994,613790,459879,404837,64086,596718,207921,401911,577727,284023,301199,210114,392689,185386,876410,350485,964635,129439,867344,38116,473870,559844,804337,636086,164590,960115,912611,739793,958775,617625,498114,492435,652878,216338,765990,694300,254125,68333,653280,517202,769915,264350,502147,866068,28675,867017,284367,558690,659976,845331,583732,922928,409984,309747,596235,209669,32624,823718,33609,655005,194539,322190,127227,870465,857175,71981,64877,401795,580331,83207,15634,449198,440613,67212,517272,234554,557048,200047,879032,190391,974461,807875,583097,916161,772973,981084,254366,292824,40234,975222,79395,753932,488312,635928,969227,80192,813473,738146,301231,557195,592631,650168,17654,316838,231043,86123,770035,211861,548854,29055,49905,671686,41669,478540,227105,489269,289710,729206,350150,684714,613407,568079,772239,339691,375291,140816,770015,863814,831058,539884,683849,735618,357141,260841,476666,462405,135976,197329,572429,207492,780725,872489,910913,759883,998898,248617,176033,77763,960802,639218,279853,711911,910976,184430,104797,51668,704211,920218,319843,198211,123155,927162,705850,165488,783481,145239,604960,789154,821463,460744,302425,546945,574733,825258,675498,299087,491760,17516,951541,568357,847324,466517,92965,646288,548719,277919,972766,333740,426672,565738,433342,526954,474964,83653,378746,625790,231935,912042,532701,777327,812418,984876,761427,412136,725218,205012,296526,473856,469459,693274,566779,853271,492891,347936,644844,349377,53257,489546,970921,526209,421526,693935,190034,92751,741119,672472,891141,22906,926358,246287,442006,960860,543731,794029,278717,490341,313167,211296,420765,731555,649349,272001,474267,864068,134620,804108,421480,752149,204457,423846,876667,355124,681355,434661,190882,170404,731523,950652,248313,161776,644453,143199,687938,534562,292719,920336,554015,100684,23561,30292,467053,852980,668315,513154,837850,422834,31376,449041,540434,30111,144208,278880,66789,429976,642615,575006,769267,661195,326880,736413,57596,587625,771893,706469,30099,30894,80080,789435,257607,104603,123931,389487,448707,13099,184366,522267,661196,766677,876735,880754,729099,689526,719673,233251,916577,312044,815605,449225,637688,404224,227994,542073,672489,149339,779875,875986,972216,48476,63318,625908,6781,631315,152944,530793,128822,129884,880758,999026,691738,111052,514156,312053,619631,653785,124565,990524,140669,891940,972514,20456,769893,151193,21783,271957,185960,660754,133102,627864,486706,997852,931576,811717,281165,368216,284850,817109,343739,519690,211908,762134,283284,34303,14669,709768,476503,563840,633291,775066,285948,48740,335812,697514,926515,683612,948882,739450,861873,738068,490500,805713,175478,814469,611575,229974,857246,405504,454612,418426,728706,817780,506990,66151,321225,572760,736029,488456,934647,567719,613749,105745,71929,419599,375843,995973,789495,356552,840803,170538,39842,687533,168225,652048,662808,166452,368104,687375,580004,28936,580674,5030,799481,118611,39388,84149,605525,694576,80625,837527,91042,889315,662305,129487,650736,252199,590621,473979,327338,675669,464852,135961,892665,99167,578986,849985,437682,335173,904863,292186,659833,134974,827439,635822,874227,963173,246008,99250,536554,63714,697125,272604,835119,311172,550901,491821,603356,885486,547271,5976,778971,514250,115486,295303,626278,283710,106902,824650,95833,350331,157770,761140,951472,291484,741454,189975,283874,616936,362548,575798,10598,625387,8022,929958,464412,296086,770588,757731,735175,318260,820840,258206,539640,678029,216539,649040,223408,146186,647245,366085,389450,367644,25624,483017,190243,700253,173849,248034,376505,88650,480191,437802,931335,710190,779460,79385,22258,894556,291784,9384,240645,514378,653757,296415,762668,140031,523401,480292,45370,53074,455224,685902,392276,321849,969391,396847,415776,432924,99565,1067,306575,788359,386868,742135,605738,629717,869831,456494,197510,163948,143105,864328,533525,569884,201072,308501,887904,524433,631264,339080,31990,876216,261141,108964,333231,628486,67925,673433,863402,616118,868873,826654,424879,412975,374914,81873,575859,413831,334938,304553,668311,834740,717742,594535,754411,985526,293230,650058,421458,67199,489514,356387,705479,524119,472268,734040,761380,819611,858814,255069,258732,631447,369255,58924,81534,591379,882347,75896,376127,630406,71493,44708,558748,831029,749732,666999,171649,767493,928841,341284,132730,929647,748264,75704,223687,498946,398326,494919,25668,293974,529133,743125,740363,20302,886801,652544,30118,877332,551882,802802,321657,220608,46212,57106,12867,948452,969661,603856,771125,651852,724523,197079,777191,333082,35126,400453,571727,295607,410951,896547,187675,893977,955646,297360,230964,562186,113312,117006,120426,327565,192942,627375,620506,88894,647450,327271,617859,827359,165875,411067,977909,215720,344231,561124,776708,799338,784430,539833,632298,936895,197692,78037,617429,966514,846093,506156,359903,203269,955200,788016,802153,353206,843617,64839,291541,810198,569806,760662,612852,688836,638868,409017,71334,739250,376779,202849,96956,203179,113599,414476,351188,764328,579095,384914,904187,446776,271550,776248,877449,199117,289797,948650,763831,993806,466523,903292,868428,72219,363838,404908,669968,629366,961604,307825,32715,193918,47280,93907,625564,200858,416765,436398,283257,81139,103547,214468,169462,421561,494855,611131,304118,106444,685922,353341,925466,64152,604597,787724,515871,51670,898687,420375,976782,968869,987577,855187,698910,601465,201997,277593,929625,509297,155762,724684,970196,369368,64808,579689,252384,222794,748204,654552,338607,938353,270852,810925,110149,927191,746662,573740,753291,389093,58099,29864,297770,58741,689432,106329,997359,211542,403186,798689,483703,347815,55716,618359,124240,33810,263778,598937,381545,252751,334145,749681,888129,378383,874100,923620,145587,438575,487525,41264,148162,600237,629332,981962,276819,257507,720619,913665,649448,515473,558956,784229,169365,223584,194797,947491,124961,220163,916964,393251,383018,188015,615394,797844,284891,389194,203979,911068,742517,719358,798374,88936,287962,208206,384885,660624,879897,311384,664079,321925,557023,933845,9990,38647,278587,598319,316227,449019,610943,723982,903705,860536,552770,317262,495107,689575,941128,735453,941460,994204,787920,771952,359576,425764,161188,567396,575243,171670,788403,199099,526476,144349,903825,330695,475139,446603,19032,651661,406149,832096,208281,69189,46480,462039,233906,227350,300204,972414,975359,685919,433389,926157,559308,607028,767618,545019,934982,612905,219656,805505,525155,692771,814105,806654,602367,268892,136378,594877,230625,383446,663590,780157,630048,59025,61882,387501,925854,36774,89119,982371,303001,454462,315756,562449,804154,562,572091,282784,247977,67688,53683,800845,814515,451220,907021,27220,247127,716874,446717,84332,491653,423487,322746,967512,418215,209205,524889,822946,165373,583159,904993,582353,656205,386157,280130,261595,90250,751428,359903,552906,174493,745535,594429,750994,995475,657949,963775,459765,413027,391379,270084,723176,876096,922967,513565,629600,378615,134056,141141,321535,161143,418985,87472,88207,949288,193004,935502,749486,925024,866845,446749,331761,39600,275966,326044,212038,287374,189133,812765,59534,61533,308152,926520,794754,565068,888070,57395,439106,441491,605528,428760,486510,507471,44439,970435,84873,166688,751180,272525,720232,496453,18155,259270,33370,834515,581906,695459,851093,559316,326870,600131,743992,233561,568894,140700,408667,512908,590768,405559,561459,502950,551529,320911,827800,922229,858732,961393,374412,584409,795602,398644,262192,199897,689298,231826,510698,995321,774379,236596,655353,430128,127784,599533,45637,953783,738038,911365,500048,608884,660624,41586,731644,9964,168627,586509,357346,922171,291689,890528,618577,770961,801648,351380,155468,713984,832322,117923,691214,775954,976454,223045,3939,738727,425638,519941,252362,327786,928840,140277,263156,812633,890739,896010,757853,33008,699500,715476,129185,433389,892541,787359,712567,195911,247307,492584,5535,950618,489210,664614,674523,384041,264121,603957,208815,804780,320268,75439,422667,830717,751704,220366,606412,251427,751235,446455,559728,555778,769432,608646,147738,315795,26824,763639,421,586864,532523,150472,570228,134634,892774,967488,366547,261152,170024,652240,200280,427586,322907,623030,623365,19562,745548,299900,244506,636221,747110,756714,232727,347565,601280,137287,940865,79781,851361,751001,138869,910766,971975,908106,952322,519391,602317,235079,119936,253732,923246,187503,292707,126507,509598,163907,431424,456566,613354,179356,423282,512071,37760,80819,975330,77189,57176,791470,303015,418088,615446,705623,320471,308802,848711,421389,782941,198137,632732,883874,262408,996569,38860,975650,482477,17237,245632,132259,119247,199790,50736,269881,762137,562554,724421,820534,630902,298326,868009,440661,624269,242030,219705,616440,101065,251620,463887,668701,881721,728925,146726,683497,648453,987687,302014,2524,790124,453819,868198,459907,995106,99888,849162,819871,178713,417930,502295,800020,705759,852743,730262,527439,96994,230732,929354,562121,898907,586873,349719,42435,579497,829467,693991,737507,829031,280998,553326,559145,166037,823771,557511,901995,976061,328321,582876,914140,532563,556032,10995,628024,509793,994123,121587,330895,315069,426514,462329,401612,886308,333628,565003,744693,791239,183792,815049,78580,584996,336341,115692,356326,336379,690213,58987,966817,328098,731193,790663,688531,427728,350387,401669,418891,82577,100523,856424,838244,612054,880977,633611,270349,861311,141682,88009,78692,43188,943899,889452,743680,361823,988119,163216,754037,391341,339034,577905,900703,441293,534254,747933,343469,214207,115571,743407,959568,548052,78411,892510,541475,988180,660037,929713,825487,327637,611942,44810,333392,50752,97973,591736,682042,346578,909589,353835,479438,407882,533615,427132,632313,445545,959797,654862,967937,608242,238321,598143,145669,143366,769108,638510,778024,491538,256260,19991,485525,280168,660341,432264,871988,466841,495567,152573,364131,907467,411605,958852,158104,932464,312539,257522,506852,178785,627650,902492,914099,952909,326682,24614,750562,475438,840668,670304,338083,877550,827475,90268,469786,131409,578489,302199,602044,690584,687577,616523,260809,25831,671175,494631,778756,669941,424502,183133,903206,764242,794876,460481,569902,334728,337347,24199,310702,239633,4190,961424,67700,938794,743908,51982,870008,343325,511568,556860,585471,229958,284120,423824,44229,502453,348299,979521,626701,141296,767656,621652,186995,407874,653391,388854,789669,132462,639924,714569,320878,893546,323543,509524,382302,100276,258159,372402,883213,4277,991812,304651,514288,337759,716379,225792,291157,534071,308094,299330,184845,30122,382554,723368,87507,127843,416999,617211,727539,865990,969276,776839,721611,2282,882138,694780,882856,505921,696531,205349,626529,191053,920922,747334,32608,883725,624198,8903,873060,671819,19183,474177,264009,737628,180959,729430,579122,68727,487968,107723,222399,206815,790567,522184,235260,969962,280530,280301,321937,769600,288196,203760,57815,106577,232241,776581,239245,52844,255283,788531,871855,875442,930083,552366,180383,778167,584958,990455,653894,536698,988591,323567,418600,135527,222130,485670,393056,181783,672786,930563,168141,336431,164404,169513,327538,948011,976904,304367,995332,265661,496117,726733,135237,925495,211983,346249,881377,670420,499242,703245,333005,321122,149793,538979,228663,461492,675223,262110,555646,1434,944398,9421,236601,628425,296632,750670,445904,835777,405562,358709,145838,265599,160556,109192,877751,471258,987641,45417,517294,233869,745798,830520,249460,964708,375588,131349,225865,802891,633491,360487,134036,602035,158644,705457,305050,388487,913936,712448,754309,374808,386655,567580,621715,965267,512449,605666,449737,190577,475988,452323,535201,45148,945693,543758,650785,35267,686763,886313,411378,562070,342543,234378,504870,979776,68150,114189,105161,3574,740037,44188,688468,1302,604288,658357,781513,979610,506470,764354,346910,59078,858029,849518,924790,831632,522375,369825,56887,104862,586231,50059,274540,615746,48155,495673,2214,425438,42973,339224,57782,983238,159499,606618,935557,819305,649881,714035,874102,930195,194624,717232,346191,916383,313176,418389,96757,914701,316975,262815,515698,442350,345649,82835,67737,365540,370088,588578,946211,612084,559225,724478,485769,92062,288789,605292,813312,622341,706005,339617,749369,653663,351501,350279,468019,834880,610745,248123,404150,799670,663652,279156,632045,104469,930006,925464,739495,849041,369865,191927,755145,205875,408808,877704,543450,358692,622355,219060,212010,707992,172084,496648,335087,744217,754843,643159,595521,229994,393561,715216,192458,123991,54768,584229,524542,481834,874896,282444,149118,750606,397747,379004,867698,317087,60707,339913,365468,748672,805960,20114,788301,203946,508697,420883,187291,421379,222404,871160,539730,215136,272435,312896,52813,482963,571743,610963,93968,991784,795733,570803,956418,363593,358116,311981,506427,305387,259641,822583,337560,186279,628776,987383,267182,626224,514872,542776,644036,90580,477623,593741,96602,190086,838513,594983,161840,205045,293721,84028,760943,381814,661593,24832,921867,961857,894035,77936,929527,741941,998069,97810,870892,951418,833754,513990,179110,783113,810942,692256,368735,248368,868438,874629,358842,804141,152056,534927,811956,498152,92132,393956,981401,979192,878989,254824,452106,537647,326031,510513,410375,404274,281760,904284,789150,896858,485347,287987,567686,274533,92169,324330,967702,620548,778758,333963,473152,234472,49107,130232,169422,670872,58158,850784,895324,905214,4151,563420,626608,378587,117141,765634,517418,919335,617360,161855,190828,598054,776160,958526,854454,683773,849670,881878,168848,635034,807239,168722,902693,658384,63244,338212,709657,778215,533396,113799,891074,704076,64078,67924,730086,961861,787038,502940,749506,866796,965136,161806,346822,607052,409492,23404,753626,104232,859036,36216,400179,267378,697958,435186,898822,293807,928210,972687,764350,747743,621975,895932,216459,150379,855694,960960,39846,797192,106160,8902,213117,623391,157002,670233,386363,981991,627528,980198,415135,617757,620720,60625,627867,834487,16891,853225,195904,427842,42979,579604,591449,116645,482503,104517,57414,122551,5070,618584,762662,749084,213619,110723,52409,520215,697087,936427,33824,271914,613581,214276,79788,903778,739798,411910,200346,113366,842788,969547,666651,697526,985200,917132,544229,648357,111819,437344,175196,391479,922457,16952,232860,341285,414332,232553,134335,208160,193333,731430,892615,678698,215062,396483,41806,213174,158094,705649,561158,250123,556425,452517,276491,838292,257922,886287,861983,484517,667928,175972,877333,858255,240681,668902,111304,802680,1137,410127,266926,241887,983706,75024,429650,936087,15980,225716,440442,260753,500075,146501,464676,43037,249401,504185,157270,134326,20467,56823,430030,945361,620886,235920,482981,483244,248136,336668,983058,59722,468389,303831,278271,727098,94744,141632,424416,585531,571965,791254,45821,925532,487792,780940,904442,753487,471469,193398,94108,90045,546773,42872,3280,294088,317871,534388,926314,199383,771069,369277,901461,871107,398811,348109,325929,517701,147240,255855,848274,106700,847580,896953,682431,799231,556634,752301,43930,677257,211139,519298,910623,60705,7062,833920,510246,257157,278021,190586,968836,497319,294127,864524,333961,147121,773479,528271,886397,932299,408664,915116,339700,366400,203241,484148,3694,602681,66182,394993,578627,509322,635981,962551,660560,182794,435333,163391,860142,715326,988060,209197,320985,624135,405134,441837,224225,329735,768997,977110,916207,588124,554084,537684,8678,474130,30108,317540,206012,295104,95818,985268,580652,502515,329499,970925,121576,962548,801999,395315,126158,115886,576841,344471,172753,92428,749650,540759,324784,9705,309507,323789,486816,568251,704137,699486,322537,271710,283686,991527,3562,974651,279507,37247,898282,947281,689631,720719,347250,620262,737922,409755,341796,226106,4063,88922,754806,234215,724510,710539,285556,431197,687964,954378,157701,27263,741131,807450,160117,990586,264182,499659,738112,451940,605336,726214,409759,788552,94480,35871,309802,472596,911716,902442,353205,56188,882450,535094,254681,49185,389878,454002,464202,326828,863080,977456,629460,650041,995884,818106,164568,242638,267570,106255,622171,745253,753186,537874,678053,407225,5265,270833,865975,833162,555859,18385,506145,470653,376322,949499,820969,298086,231308,52802,2777,908186,315263,674914,398180,930064,498937,580896,517750,126815,875690,491915,12680,121503,390994,747063,966241,153827,154862,850203,136726,64978,934183,338180,739629,193870,62510,683276,403680,41731,511520,873899,325040,408644,972831,214722,572613,83281,95415,691927,393565,188122,806322,685907,773168,851200,455690,405266,582206,49291,76198,78622,561357,268023,150928,989679,448175,977437,939514,387217,322469,203920,630175,248253,671885,449683,16954,560725,958444,320632,119608,547506,317191,826879,92620,958392,590483,275058,367926,854902,487816,155929,690180,372485,307463,670182,782019,942601,546200,71996,650400,319976,256843,971159,918992,827456,336922,973881,124603,199973,689903,91135,478143,447673,455912,950230,496654,692726,505002,517341,559466,90077,114398,988872,138369,250721,647611,661647,337743,231212,585842,532472,51084,232362,945823,637842,531421,380717,27453,542261,545919,398074,99012,181016,351475,800855,946418,925212,840155,217755,736977,118308,652003,647915,553161,767984,385038,11255,735922,858518,667008,475788,900594,415110,698226,373742,521803,715473,342666,283859,894453,913421,697979,720569,336742,289837,139012,294227,793443,952270,629354,54438,143504,342279,437846,205815,732083,7367,690854,230338,584780,645404,584500,413213,967228,604977,711068,261696,454040,427191,248311,292915,274630,727819,925435,700266,848661,894097,215630,1287,963364,883797,387437,716331,234039,426311,412049,950312,183449,317349,954201,133009,527709,38628,421654,50535,92850,793995,228292,474295,204357,981680,696426,628260,926183,4123,584011,339078,763622,931809,754844,379248,741633,976360,286823,691316,996952,964406,558305,976819,642913,670532,909063,626030,321872,262603,851823,571898,556971,276585,730130,632926,115132,997919,525290,487080,550791,970129,906328,309838,3059,539325,15263,684113,508854,882644,567154,189332,93140,350600,569698,134997,333913,25137,36171,641550,230857,712753,481445,457466,973441,511102,291626,21998,173705,540506,506981,912176,927307,95751,17876,278006,855251,265451,562229,208760,8582,294965,507770,641979,404042,838246,184180,605377,928426,82486,918734,938340,192032,936229,93117,989597,638671,395544,99328,408098,169602,894373,519304,705480,736600,261712,641753,343511,795979,430137,199842,917141,910929,420965,902976,901427,407457,422269,739968,457913,925844,313722,229223,366051,934395,391875,392385,354664,325740,278450,276132,576915,388656,855638,620666,969106,410901,865421,658185,440584,901876,788618,418004,120936,740934,143937,398088,836364,32518,494576,878500,647258,973157,376635,893761,213106,69008,553643,433469,157969,491992,995129,321380,611490,638591,477663,980777,380470,988734,719044,335309,21983,833449,529809,751521,910619,852713,582393,420611,792183,906758,659540,118840,737101,385987,282001,42594,441198,290066,734093,650766,662083,639502,53694,853260,54243,119713,889017,232016,185481,240205,374646,786262,926688,807576,895931,336108,878867,676564,676006,182278,586154,961710,308416,807021,707663,895273,484534,140718,382476,131711,840301,455585,324144,369222,265332,513883,197177,798832,391207,145356,143048,965040,395358,551007,687146,401090,10277,950710,974657,764043,505815,223605,565689,149856,895305,883766,102498,109505,932649,621423,968301,402919,321660,567196,752500,66861,279291,990405,179463,815058,551786,48959,811810,881482,917820,257155,401923,406866,424188,14551,807945,680902,513016,752973,10278,702964,823794,431145,64460,916240,953530,354046,821459,842480,72697,480158,574447,204674,782252,700022,756622,119327,131610,375760,425636,615192,600018,492036,459305,428497,217277,876271,843061,244282,661150,989988,749297,986554,591502,396875,121495,194143,395989,597593,675733,145385,587671,623034,196867,266940,360933,486051,586628,677402,70578,322974,767102,123498,807979,623968,92528,917481,423405,432114,116858,517511,176269,98259,629482,945027,437091,260249,153601,199042,446001,810401,773100,273221,885328,61021,115848,440569,522251,202777,374264,832347,206340,839919,951768,906940,577983,700228,147106,538388,367427,317313,632324,740844,270532,215966,965672,703960,716157,412425,387474,552599,714028,532980,914547,410322,997253,937714,15020,607973,797123,161870,559545,885882,735159,799354,330695,483380,911460,389203,412553,228762,716794,962931,166606,272820,335882,995239,618792,702010,571507,180735,496327,14941,434628,857604,93412,530134,318556,233938,179692,332138,120551,253805,977053,120868,763795,365177,793927,372998,277407,170369,667669,223637,350068,529894,852150,998449,629099,463039,266484,889973,742375,560380,441324,475812,801332,133652,103694,529692,154502,681373,427020,658169,30971,102928,668159,242020,421010,970060,698587,736126,227118,358562,463595,643318,852296,622424,859413,417161,516956,493971,347342,867503,379660,264345,664518,923804,343230,824772,77327,592275,831708,56556,324890,273228,607173,78056,662324,245757,718236,724396,940804,939093,486800,913858,301602,894940,749635,330459,513148,466518,537385,35532,181158,6368,127278,246004,467539,25850,735305,703053,871374,293503,504483,527248,838858,648494,817525,498086,7953,275389,372628,870246,103670,449353,599452,495469,951625,277684,554132,867070,203681,288089,984972,137307,945954,432428,613779,612793,674842,309513,573603,626859,286762,60890,764253,494459,105263,70483,627169,20502,67562,203600,711589,495252,757792,474236,502235,632384,779590,463986,564901,283435,934876,859227,11664,528803,32379,177336,863779,809396,718218,593337,604758,600022,252403,469204,988329,172616,931814,379176,115242,347886,584903,229240,325001,535495,841550,475187,513997,679718,628227,644049,79779,629801,625916,963851,447872,783453,731424,289769,508708,308735,915187,238232,695660,212973,633380,221897,167048,808904,946041,305538,574681,946316,63072,647883,688453,877199,804910,705277,440658,555339,712144,471037,755711,721023,505952,83834,298013,77200,967484,230406,451278,173239,874511,380484,200668,789769,400162,398465,259720,539161,202177,959951,466621,13370,793109,541695,416148,121981,351263,626454,598787,838363,951788,250578,29454,718070,66180,122064,393931,374881,655994,504761,911521,872366,408284,79729,98697,783872,668485,635100,352262,383853,277600,869345,606967,467589,59066,720490,728822,654946,232281,240804,235110,632501,833348,760838,747357,559717,975025,825748,719095,16872,293834,39582,203708,946374,947029,731545,483274,56466,478793,184143,197004,580381,798980,549304,931030,167553,511926,424828,624015,206446,428618,74504,574504,859723,498681,793582,52151,226727,81664,765850,431874,158962,345419,177399,382048,895650,444591,68679,76503,429381,540114,509212,712595,592540,185351,578397,923809,114523,99651,64925,228426,363811,212508,930820,310497,986516,663669,977761,986402,411728,709263,472914,67455,720091,619892,986818,20603,679749,902297,116886,493557,48704,277686,149795,339944,432165,740280,408783,244269,148066,954696,553422,445816,315268,252988,158342,164449,776118,624113,833004,876766,67465,361017,756947,207307,792463,487313,14689,175274,898978,408039,319462,687305,798852,516769,976811,518706,898116,107704,245825,613931,711403,797638,109724,155540,180914,247555,483423,184464,533238,923442,90565,543852,207759,678312,763323,336896,971315,32324,490846,178872,326152,592340,683246,865792,134369,812579,347100,344538,13976,992048,786429,164258,583126,226263,403655,796675,631705,949369,645728,950274,833237,854713,22577,928473,386347,7532,700521,379443,996190,652778,596458,850747,600195,110572,343543,347504,781106,309223,379320,613127,740634,725364,815233,818960,445983,784036,763308,675342,359079,812025,680623,999865,813067,760298,913784,763970,580089,174248,363238,208233,430124,859714,723703,403408,461518,216457,264439,844105,361709,495351,150067,605957,607536,529435,314732,942607,205450,794844,35874,362228,963989,652800,996134,6451,554602,806733,16710,550856,526198,605043,158574,125090,4537,925616,700018,787033,943748,750262,952251,476256,535539,740139,563295,258278,356297,356877,639012,626528,193505,55381,826739,453306,323753,388245,603642,964663,950514,226955,121659,226927,890823,112516,579226,440481,151861,598724,691686,26594,184205,782936,896193,912877,103070,110187,166371,273177,426293,178345,194186,825057,504668,641778,964802,745100,797742,39382,203437,273324,894058,136988,215089,21941,279558,184932,718778,298688,263985,370953,191771,214968,39577,335637,890770,931615,480459,494765,107383,244521,258933,190026,723985,998426,796682,587532,49097,253696,852568,452986,115793,713345,469378,251189,11500,227079,914556,388518,50878,836406,934579,8257,143669,360264,226179,475224,709379,40148,19357,47963,385221,939983,26345,765802,75379,108940,248874,162858,676508,898627,527238,86615,643109,114633,607736,454840,116557,231906,515852,108871,566520,74260,514388,134495,672977,261151,760707,894912,392846,501003,869312,257532,124137,457760,605447,575468,338222,433460,29423,682723,270134,319551,795694,619910,195054,618513,230325,53507,769999,509660,84961,30211,986222,710941,698550,320847,576459,28061,439164,399333,413992,505337,924597,639212,853388,503899,152198,569860,553079,343253,821440,85265,370285,500653,856147,101663,682241,442323,17497,474388,73294,114739,17325,669465,835932,410458,439817,875322,593539,368255,102192,294331,849620,261126,333709,757862,64730,670654,144467,77563,799062,457409,284724,61700,823619,580567,100592,391579,580536,563416,770942,560572,334600,478785,70251,478127,791685,752061,992762,776898,199253,196861,201225,264879,45284,91344,978920,347944,941817,844584,67263,963238,373520,853256,990787,176144,783581,41317,387699,866497,970953,600219,634371,573614,257294,977887,8962,532797,76994,447431,441347,480077,335907,427398,808596,634838,532080,218356,683636,773826,20743,145851,831929,783479,896585,588654,67214,453174,768964,755200,223162,540140,876490,470964,608,900466,414991,52934,156524,391832,333866,552417,34071,855813,606891,817832,887712,171791,658085,887287,769990,716260,38344,986018,144698,127331,687217,596543,476133,465883,4130,129908,301423,643805,31725,658579,451285,267626,6096,505677,558139,525748,644899,584563,764028,168938,898153,916807,320716,355030,593858,476690,936957,635907,519977,94981,771963,461713,650628,653728,995836,866234,928578,496705,982232,971519,421917,592594,683804,592668,753496,66434,238045,69186,56186,827166,204185,195025,989795,616010,617170,523555,66334,583455,273507,248766,948895,426633,38007,239491,1753,912102,713531,187901,210907,956736,359162,486738,958180,278959,669549,868734,91963,930223,43386,97271,175874,319239,478653,45972,643508,211096,408911,591389,856085,61740,648751,742528,686994,553119,209264,770113,867949,403218,542909,806048,101882,176929,971047,675686,205475,897770,643599,928675,271208,945288,813038,20068,774874,685171,719465,815101,447415,499453,335116,839737,959258,286180,168058,223231,272827,983564,250515,425320,769948,54453,536134,454799,374007,712047,495909,21769,933051,182542,261477,199616,875674,378211,329316,862117,631793,566810,279742,783353,276797,749668,839777,998148,677228,794597,809246,415736,204081,480185,440799,290789,272578,929621,676876,549551,623539,283684,936752,139830,215662,920757,357675,336768,41657,39692,892596,857260,585827,655124,7512,103693,539762,650377,338866,375203,655450,367816,947935,203757,279214,710830,47039,836648,880598,71770,600213,511852,333679,229330,576566,448035,732261,406334,838218,903181,209159,30241,482248,671599,113831,225311,411881,771378,891680,177931,555182,819107,169831,203624,952110,224012,627508,514722,608744,41858,667974,261568,881736,203663,609962,676470,599417,580949,118485,635313,607066,61348,532020,159595,675407,815116,713103,702629,305028,735230,404418,522525,246096,55772,523703,50416,995345,493187,794205,767888,395641,849918,738964,302009,432476,258899,968824,995215,127332,713602,946097,610797,162419,985212,550508,698438,134370,211559,624349,560155,406269,808301,946215,474436,421684,659174,227571,96998,874959,434829,318150,751537,364548,145591,668648,717643,120659,774465,661288,180805,204597,644954,856333,844535,387975,182271,87579,31843,69739,65078,129065,631808,83330,265936,272307,388794,429977,431513,834170,765023,91909,660368,482659,705484,124987,422402,723330,197740,299043,790621,865287,798030,621402,7299,377040,946946,951911,126241,317249,537977,467495,207919,297849,113323,940525,966699,288419,458761,255640,665369,589653,852191,332753,675009,777930,927666,446251,42973,561828,929800,911254,94550,695383,648167,638,374036,393409,397019,436568,973361,775091,621473,690924,739378,206807,478511,36643,838595,702742,728659,927897,370859,174409,644665,545345,602634,923977,994316,332524,743486,347301,147426,868578,610487,461261,307721,613431,156629,976306,322921,690688,618801,337815,863730,982885,700842,191565,819541,773950,9583,13142,828175,73929,652626,924754,657159,105941,544865,40410,880756,528270,742419,637491,673650,732297,74979,886703,664390,295929,493770,945412,286166,202537,245808,890801,483614,888092,927536,597274,172942,314160,617013,127564,626598,611352,771755,61276,318159,929673,363707,411295,684168,300178,477811,68590,299273,755173,385881,185162,252421,743165,680455,455431,98404,370171,559076,869770,758091,682443,551246,544188,427301,414786,54084,259695,782109,570993,37227,589847,56449,344808,821556,451505,526178,153234,133754,889339,429779,526474,947051,227493,696658,119629,163447,676395,616640,294600,409324,766614,476642,163338,945747,768078,290915,74859,379024,810171,667562,771842,77805,531159,663400,68185,501907,458545,823746,945637,850803,752258,340770,554333,334768,727558,456367,896708,338702,574065,856398,257706,918245,71679,154017,24774,24103,394754,114907,427140,346612,983587,758747,251664,350596,843359,329167,485196,866949,332726,622892,610291,360979,652277,608640,151251,41963,393741,860120,558177,985458,532781,171137,279674,250807,368932,815833,304487,312176,520518,978259,269677,248419,420488,70097,366393,364363,635532,360141,219131,754345,787961,905448,459411,941510,107968,918402,824838,583041,506884,536860,681808,957205,53240,235906,164744,79990,119182,529661,200963,300481,262258,213897,29381,485437,773519,301191,716385,655125,497541,228552,205545,671269,516288,436722,331644,794522,834916,929470,778420,829070,394455,154652,104823,671370,555033,835929,71680,784737,436250,329657,268192,273645,444558,975697,652202,660518,498138,250095,150407,448533,160375,187115,25321,503049,848938,922756,420260,490301,803302,618656,363649,27078,483558,153505,298545,290132,182698,971080,448774,324275,187755,219455,697801,231472,662058,82101,129432,867102,572425,608636,315421,963669,670196,632463,110522,38125,937098,522863,320468,78993,499204,618799,281266,610573,286927,852725,306973,822611,757599,718021,974198,99884,151328,534233,719905,609027,365109,537223,279634,269075,974601,325113,557345,274531,118134,133065,737436,256863,656348,306229,750768,105333,179423,354831,282741,406308,496387,801824,92647,655436,188821,64531,525708,94021,792303,869984,281104,365558,279912,189110,628762,600080,354682,225190,965685,310872,324810,487158,622692,986892,780750,181865,335240,532483,665528,955217,836264,601872,308543,117754,575032,920286,946135,500314,213399,26685,590161,900727,199012,82516,9850,26654,485577,691126,506428,824513,464597,290456,767155,975375,638802,721874,884570,447910,92970,894446,810051,412905,133191,466710,313996,55771,594295,3414,892096,423914,869395,705780,646611,62528,774281,877622,366637,436721,437943,623927,313796,751757,406118,864025,375501,343742,348352,652268,70335,625476,266917,560331,20851,976676,8866,704411,124741,553627,527342,635216,866720,6079,664183,888522,999977,551775,278294,924101,549934,976223,591115,405503,323561,968296,844724,524361,301320,242528,754945,502856,924448,476041,441232,985688,318893,662712,218550,373331,791513,139822,606627,265660,222082,666080,329012,410386,422000,174317,987454,399143,327272,179726,964311,293869,418352,328111,339917,505837,398206,39023,667611,202933,131370,921166,10008,59223,3406,760300,691917,68890,119247,32943,196828,591783,670706,935836,42811,795938,100037,649330,238074,514840,640880,844774,367280,513665,635068,137065,916111,400312,277773,813664,285474,633318,476585,643650,752941,17484,591257,807802,890006,740142,425185,946389,893176,145462,136096,326768,684342,917564,730104,235911,311269,454743,339056,316199,754687,194187,955168,170259,637577,862131,508722,442417,20483,495405,992341,752365,683567,985213,457235,682848,614538,290527,742817,649523,773544,422673,568243,550422,431167,499366,441704,313940,2768,360035,7624,466276,932013,388191,188509,111829,392231,805052,330190,625731,358509,222423,213455,955618,635756,737021,474737,416279,462834,130146,188839,474325,749233,881579,351302,569305,910211,548560,630937,266405,236934,459926,156726,723426,150852,544118,231395,136511,897514,912788,589402,968745,152302,653470,99079,955011,306632,115612,233896,913853,31781,445660,633671,382933,32744,432170,277486,579925,636137,277736,265320,959685,861924,338506,16079,472822,382474,373144,802387,661798,82857,596069,463839,30303,569005,972620,144902,439517,38024,971359,459469,719424,502504,469350,63874,747930,955671,256892,612937,348379,684582,408867,121241,839832,488042,320222,374885,937290,713531,545815,56520,273207,422949,470586,707661,421076,286379,658012,825462,504221,521032,862377,388946,715634,413875,634634,830168,545467,129410,516950,361699,109834,508888,569769,759873,80878,959676,898377,85888,944092,366444,377719,708393,20226,409764,646760,863475,84135,60224,337322,70353,900458,944783,489504,636077,821106,291207,402656,414004,79599,330274,537692,793147,739508,430228,757309,231416,636654,425704,867360,174789,408991,897327,624937,418423,962832,521562,808926,61626,676463,981755,480655,976647,373564,421577,243862,747056,205148,545213,652819,604794,590663,398929,762234,682669,845529,669153,286933,529879,152797,499098,846342,443818,449213,240158,758195,220485,537456,401203,795327,424120,426989,458764,387116,699689,781385,531549,959642,178349,189353,194953,307214,126744,457196,958385,575962,812445,829516,330117,58837,467570,852054,449378,534986,413777,247042,598365,825241,817213,621006,620714,348472,553083,850446,696347,42817,95134,380357,175749,336043,728159,978317,739723,776935,402499,504655,796948,716516,427916,189046,549152,622782,423128,278862,916883,928044,582573,547444,391435,812005,571930,614170,752632,539850,375182,768488,426864,913485,128391,325337,682989,215899,993461,465458,293547,383074,321823,342962,269172,93434,285764,691908,340515,826727,663919,283915,624075,844011,633709,639563,356353,78781,665009,116969,183907,688772,49456,795614,506873,379576,288469,642326,430175,678525,348829,828955,164841,696785,270913,655630,314057,687574,96843,356423,839027,954970,446321,521112,694495,941654,190303,173211,440738,621782,564801,35510,601822,786698,902399,319519,912969,610964,851437,531197,379746,284047,767544,113483,136550,511074,858447,854949,875624,152828,831762,523000,534281,372637,717913,215032,410876,92760,19002,201224,103047,823061,583877,92048,955971,859459,785197,215397,699197,748457,520747,739014,264083,368119,601034,256175,916871,658528,676841,477189,135992,157594,457436,788312,221778,232201,876662,637173,628357,179291,912713,592379,122314,435229,314508,733150,414183,718788,281967,625650,842990,222716,789129,52672,108887,913102,347902,784162,194109,53137,952063,484569,41588,398019,82141,36930,441162,144497,471897,551403,263688,361332,950352,606137,138501,218920,664253,991640,526403,315813,571982,767279,870600,742975,23112,592445,848187,806746,674042,452086,851804,64304,757675,676466,334461,102280,100101,557025,193550,343956,398453,855828,564179,340210,560951,219887,397781,558813,73871,340273,260891,52991,864326,493288,321147,3715,733835,710202,635566,766183,443903,174467,708716,511585,767605,262635,927238,664770,434243,28306,902182,637669,254304,550127,169120,279362,232586,739181,790764,555424,408898,959236,800784,630566,564134,469288,464313,403118,130768,494872,718635,217615,518541,407031,814721,462566,224210,582450,494152,645057,307847,307393,643587,729865,69696,705448,203427,690925,99477,717388,994476,689741,166775,945951,258434,884258,533806,925280,623042,628933,46265,903690,677895,774644,179265,826526,66474,819432,784728,680912,808394,310816,359524,354121,435174,115146,556813,738182,909281,797300,584565,584262,561041,858152,23989,35025,798573,308063,831534,196821,829867,939104,82999,348167,307372,178808,134116,985010,966507,478467,224465,903026,347496,164670,554171,607751,90342,839801,897830,873695,250833,457587,332541,240183,920742,826711,915126,811771,732776,534524,375784,761388,213463,44846,107072,401175,330323,279384,407145,257661,921060,473727,316020,717199,425743,597180,320813,478709,111351,457570,435220,71036,151792,181205,643631,821193,340798,51748,902170,854364,764294,843483,249082,922834,86058,842957,817471,112732,458766,302375,636556,182095,17685,702612,988046,296179,104954,612307,908102,562247,310789,69294,728703,79718,691138,536410,750560,552458,599375,55268,972916,657658,698463,966600,921310,102545,570610,313832,386295,729245,84323,106512,434739,597622,89192,445926,385768,16156,103342,89778,713501,179153,710049,874125,805848,196892,518495,207976,964825,521506,352324,861493,699838,836722,674637,659576,746627,448993,669292,23324,630576,517906,871653,674153,462770,215439,212973,8829,603343,532961,375858,87283,313388,328217,847988,798746,551527,776620,286391,157606,849718,719948,80887,353731,717595,172752,671225,284218,285842,562654,758658,885965,28092,495064,957830,817310,805542,483835,651155,915668,418728,345046,935689,258873,150432,948592,332781,469848,874477,78354,215552,138758,411923,946996,364404,371554,500507,353603,926937,542959,443077,650120,158213,940350,587966,217069,376345,639740,476531,104643,458288,506918,979708,334895,518967,327536,418396,4454,692964,388656,689160,162529,722198,958248,247863,544987,760086,789586,851770,566270,168696,52511,538800,459490,365046,763266,539253,801586,404325,848979,817976,55571,19393,129040,872484,506096,957616,783539,295438,248536,105813,269798,172673,5812,625104,825213,34970,209244,431246,90943,617060,235017,782156,500036,802103,261016,591862,125486,403191,221396,89019,23554,845031,415860,368478,41596,363802,635004,457783,756272,257816,300411,828660,266558,205833,756248,805300,770033,639565,703263,957921,409866,891715,806478,442438,827425,863647,512327,284115,840881,284466,98174,908111,968862,695277,793098,191747,406303,582266,579719,795909,757037,971491,343829,480125,194430,650062,346577,386053,804026,173437,898432,635397,758129,380764,950360,558895,524211,91261,673161,159881,22335,57644,322350,642135,671841,147291,409144,72182,126232,751572,608617,669781,65709,27491,111397,64146,479601,275569,636139,122852,896625,826521,468139,942925,473773,686315,431413,208968,66605,747804,67557,410587,777954,820757,97567,304271,978212,444526,70208,321403,987094,376158,803392,371825,771674,942464,348867,809450,464232,238803,155739,640088,500114,607480,243823,381624,199580,31543,952475,645524,936759,456237,555941,539018,591362,784599,205281,564353,304103,911800,14379,103541,268223,201288,223634,897312,473758,808976,631077,198368,769606,871598,291803,189929,933955,371574,808637,962549,834215,720103,240531,721401,306488,905111,570253,629427,978236,17836,432588,795612,549605,823970,926892,260893,945413,798898,745004,519643,516373,572399,219059,660536,562504,485381,251210,128740,318431,94649,714422,909326,410842,816915,181586,969990,110322,62986,22556,902764,198471,365330,593209,588286,108197,422609,849571,670043,729397,796469,489517,940744,17635,155201,853020,813964,246587,914715,811323,740059,183915,546084,663166,378422,744806,700376,468030,883271,155835,649171,80052,786152,899322,682703,422353,165132,379514,352078,42599,632263,278621,826083,937617,6166,205431,166378,46042,414058,652480,902245,20020,788703,380505,922208,531265,991698,639020,945093,68636,343073,601321,493491,356991,530262,62939,235121,705728,1546,624508,407058,545526,87302,424984,788323,12673,831050,791392,302842,26785,382536,750381,107865,275103,351338,207957,719278,747464,675173,392074,541228,892028,602826,154428,501041,406351,713118,298086,655407,326690,561698,805439,415218,474971,909470,605333,862014,249218,108790,955575,72761,91300,54095,645791,329112,953448,929015,320499,815456,193571,313871,412894,401811,312024,194864,586134,736655,510475,75562,732257,769024,158856,433349,485527,399289,420208,505469,184613,25112,706785,185782,447987,391285,384118,433809,755927,836568,917535,369849,880566,717073,827549,67409,384137,196978,709279,114915,967803,637040,843745,154744,238211,411814,577567,763365,437306,167924,288316,264832,396326,725898,693120,318501,855808,560418,910749,853761,386756,285524,292342,831484,391753,727256,818474,566232,284399,170385,440634,888638,965014,899145,609563,598566,789338,856958,407503,117639,482168,165695,447903,639292,307357,371676,270300,461465,594982,895040,448533,349218,709184,902326,813133,368908,690132,33188,243537,206332,503919,350269,535985,230061,712436,365930,923812,734110,914338,256933,852377,767033,582216,666071,20480,159065,639456,600987,852562,735136,215408,638588,382150,932597,629856,160066,77216,512954,84181,151660,199809,942244,678014,696538,444088,44926,271289,212273,675975,225578,449264,683257,73467,312201,469325,661982,71632,220028,601855,982401,357747,117622,907071,663497,786748,922462,294102,352463,313023,602019,815965,640263,916056,582339,242224,971903,512787,749190,179451,903379,848994,916966,56456,672695,562805,146559,269372,558417,285613,548323,421977,837201,804054,79191,233379,136949,940655,647622,234754,105080,898559,657017,577917,534901,541736,122750,590121,815464,997697,458812,651651,345436,660601,302620,895067,261647,949436,45734,589531,281288,750334,61308,202832,686250,579045,741101,93184,730471,744503,990779,21570,877676,457823,733905,867607,329138,305829,81383,720358,556636,23023,782004,362246,10466,618972,368285,367651,202231,532221,167216,904944,65046,653247,808615,371229,987717,556747,777728,421897,473145,739559,141486,162078,721616,61030,425370,764079,718100,257968,44718,91388,726180,764778,950182,576569,84786,851331,870751,447017,363608,35983,832388,345986,474672,642737,589049,658096,830858,830888,422586,405467,895020,448390,72397,326306,534204,994323,760431,824255,682040,166579,456033,182836,20096,408134,233611,628424,949124,974349,803003,219266,960769,617752,38400,400669,852688,218819,771767,454988,991400,953161,601677,522764,548917,184345,946714,544494,173142,152139,299637,587182,752247,922146,7874,516714,137544,576829,170858,959892,142605,335351,812694,829675,347968,756170,500064,838339,552778,655769,974321,770053,409285,424835,158410,916945,764047,897660,905450,278577,607137,223197,141772,729719,969119,766310,508786,411302,346625,190333,9803,733169,23938,674291,262804,411565,933688,789625,102342,789484,93591,529385,118668,95741,622456,542768,490591,818566,658289,569156,299279,89926,115430,366098,88972,366721,467143,514676,768373,340434,348701,379556,720810,998616,500239,751770,961767,387360,228234,702794,938884,795656,558370,757675,655779,611399,21940,520463,135218,813714,292796,681197,124355,938025,258933,939964,84458,649542,588420,332204,679518,100385,914282,34369,823610,349299,842590,492722,199824,813208,829553,868225,47732,19858,640522,426789,80472,886560,604914,973310,328378,733757,375246,503426,802413,67283,302847,372181,609333,316702,300474,23712,993040,225316,487568,335965,876579,599948,326092,957354,485737,207190,434860,767128,547460,836959,248344,268302,869425,692754,74719,460079,28580,599305,807778,441976,278912,558144,499165,337287,780875,757923,848360,862028,748330,396456,759199,750050,647043,408224,462354,358875,639622,178621,821413,815549,968292,825319,860528,488688,960740,139451,840160,300899,715985,638012,585892,378434,365401,210046,782114,21634,431518,842295,774385,446613,615367,701773,817888,393179,239771,902782,225502,344768,742372,879121,709939,235049,504892,208493,525930,661339,32699,613745,87462,969620,79155,639278,400022,836865,400002,1082,901309,522147,158551,304121,429808,627902,235493,44466,736541,401971,14579,825774,130919,386974,159506,200132,714277,43766,221265,414289,817648,990292,195853,410964,977386,958879,267601,732797,540274,55719,277452,973104,332909,318372,938821,653069,124714,383792,485641,107227,202311,676326,220913,120962,94893,506750,291845,339031,823384,442511,885502,853427,83503,405202,7721,494838,341714,498591,279969,734776,425889,358056,543725,603788,466765,53525,275931,777023,887093,569767,492892,638549,309807,864796,517424,745352,371875,384108,886378,763284,112261,77334,353345,73648,268003,528277,536833,502893,721750,278716,506147,69028,453572,788613,388026,573767,263308,839284,58211,856684,245646,162300,343604,782200,611547,757262,325120,425614,408558,991186,914154,483506,97089,481775,923355,276954,851239,85088,538443,503136,453350,594942,415515,418141,97260,326786,839124,420208,755955,102164,246899,215873,16945,773932,711558,356253,393258,534114,590227,646500,871223,409977,504313,212772,387096,981921,802771,952464,62725,736839,704237,121794,974158,308820,963871,188247,532960,524685,668645,433792,826010,245600,638375,211060,102338,386566,116648,934248,188395,439294,568117,248482,350668,452233,365610,145126,532589,997126,170592,701231,781210,703912,789952,475314,853001,797322,546244,949052,537927,139042,9955,323568,302201,458948,411444,540761,692584,136009,610095,443761,688261,4483,555278,594477,335885,430021,14370,445618,487976,336215,556545,948949,607668,178240,692103,72131,810027,641793,597120,881598,274182,827462,476676,671513,806808,84511,746600,881443,612701,960743,88992,585116,444615,902621,686968,614713,346615,114119,841380,898122,856540,550162,350828,523021,786645,649779,728343,194849,571190,332378,367394,13143,258144,978583,446007,834702,539138,764971,643142,838262,21579,484070,146331,702118,869967,385885,546446,726708,997962,600342,454934,75150,683502,921019,914954,172164,474056,372082,191963,421167,177708,816520,325813,957432,211448,182005,911316,180905,560332,811871,286923,640612,982891,273979,269397,373820,70292,252064,917218,678557,114038,282969,62803,723336,84560,319149,596114,503048,169304,818986,729291,439334,541669,483151,457896,900678,167616,963773,188151,131917,162339,27996,939212,906560,813717,406199,149780,305484,903753,239375,563428,136292,639358,464990,108451,715816,666367,814610,946236,883588,733864,485421,910943,328816,821809,644893,817467,796246,707763,322017,120479,700098,932913,672081,717850,468130,842473,948808,440264,51450,269685,170580,495655,110574,79911,542538,595553,142518,101195,388625,612920,298826,954895,96976,649951,592359,330134,431383,310366,85123,737777,976381,884845,511016,257201,305417,939081,965641,773207,943968,809740,463768,116118,655989,115893,788588,918231,890839,538863,101980,569229,146018,216845,118433,162547,647884,574259,820983,465636,821568,59412,461758,758993,548799,124604,887367,73540,294921,385611,237643,266789,38119,65383,476282,91463,914387,642746,167051,210762,25007,95217,313820,426980,852153,158663,68524,635516,640372,69140,556010,425614,19737,244557,91895,935288,405372,725397,717482,802799,627419,584433,208948,800291,176846,465984,6927,418985,437159,295786,583612,994804,670769,588409,191089,59045,306471,738189,191002,160987,988888,471522,110974,985230,505630,579552,96269,644920,638346,70318,526487,350842,637981,683975,47394,982510,422089,837330,420665,490341,756551,604239,888795,529168,165656,798275,166980,742306,978607,461446,923121,846362,282423,789836,334467,427937,734826,544249,262708,909832,517903,368261,287994,77680,545911,371297,483976,407920,36886,466334,697307,318637,593659,977179,54461,457263,287652,441938,659643,160968,156089,355639,496394,215737,882573,267390,310547,317914,921132,863453,656893,858302,337110,497815,228937,692806,803529,876663,599079,848408,203886,850813,596601,624895,643384,865162,259609,159086,810064,627510,815693,815436,747613,559247,595960,715048,900412,396208,682582,103662,502325,92550,801478,39558,481483,39153,616830,87473,854107,666555,416796,382442,756119,325335,45674,222481,66464,770722,95059,255526,170038,154410,587186,323979,990960,938789,719761,747441,517925,787198,148360,170062,157236,778282,808772,446618,413123,331942,803917,583478,11757,148562,667222,193973,772529,858403,770962,134637,204967,190967,930856,786568,769149,677766,266933,571789,236453,351468,213504,803284,365470,247537,551334,725513,573273,544334,852824,426046,552360,130462,841667,582601,700233,906249,929252,152772,995953,979986,238889,326224,342239,374962,115224,804671,649080,644116,405040,569021,599009,882340,789652,392734,328450,639773,222086,65237,814555,162530,744442,897212,939559,309541,613328,396916,606483,835662,900249,911050,842113,862268,780996,995972,496929,88221,516246,619711,314996,725500,754071,367112,249277,967438,264036,72791,288600,569123,88540,742326,111759,250038,590565,479965,787016,146444,636497,245910,346583,587116,112567,957318,830622,35170,676661,72749,669044,858807,99569,42907,170294,797814,794128,728067,682993,389828,993468,297354,256432,991000,153739,920084,119499,6007,227425,864892,725237,769890,842754,155999,271529,673598,238038,499056,302316,285765,295304,892807,891457,789214,490291,492908,34846,653224,598122,729723,956436,639495,591013,187869,210159,139755,885491,634215,234470,732707,24154,608226,547460,481404,457012,278613,353345,976114,965206,452435,833972,659095,715782,238793,506488,903661,672156,741740,228148,661439,759483,636433,965678,437407,158071,764205,670458,46547,650799,168982,646530,260164,177800,98006,701591,609167,86284,801120,570982,494511,341384,746522,513011,450983,917848,352586,458711,259069,55534,814829,870060,881544};
//        int[] nums = {197180, 567032, 701885, 294688, 49821, 319144, 793670, 35956, 30654, 462823, 954237, 828852, 85004, 156833, 193021, 362217, 197278, 327502, 82298, 521188, 951833, 265111, 760577, 510602, 668226, 3307, 908042, 352949, 860824, 129537, 908611, 25249, 417829, 291862, 465673, 534186, 369397, 683232, 173430, 18207, 82787, 876718, 391394, 475845, 722608, 190000, 969787, 233166, 662525, 607653};
        int[] nums = {3, 6, 9, 1, 100};// 1 3 6 8 100 ==> 2 3 2 92. 5 5 94 . 7  97 . 99 ==> 2 2 3 5 5 7 92 94 97
        //7 6 5 4 3 2 1

        // 8 6 4 1
        // 9 8 7
        int result = binaryFind(nums, k);
        System.out.println(result);
    }


    private static int binaryFind(int[] nums, int k) {
        Arrays.sort(nums);
        //最小的数对和最大的数对
        int l = 0, r = nums[nums.length - 1] - nums[0];
        //二分查找答案
        while (l < r) {
            int mid = (l + r) / 2;
            if (getCount(nums, mid) >= k) {//小于val的数量>=k
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
 //                         p
  //  xxxxxxxxxx  xxxxx    xxxxxxx xxxxxxxxxxxx
 //                i         i
    private static int getCount(int[] nums, int val) {
        //统计数对个数
        int ans = 0, left = 0;
        for (int i = 0; i < nums.length; i++) {
            while (left < i && nums[i] - nums[left] > val) {
                left++;
            }
            ans += i - left;
        }
        return ans;
    }

    //时间太久
    @Deprecated
    private static int smallest(int[] nums, int k) {

        int numLength = nums.length;
        nums = Arrays.stream(nums).sorted().toArray();
        int minValue = 0;
        for (int i = 0; i < numLength - 1; i++) {
            int diff = nums[i + 1] - nums[i];
            minValue = minValue < diff ? minValue : diff;
        }
        int maxValue = nums[numLength - 1] - nums[0];

        int gap = maxValue - minValue + 1;

        gap = gap < k ? gap : k;

        Map<Integer, Integer> container = new HashMap();
        int max = 0;
        int total = 0;
        int sum = 0;
        for (int i = 0; i < numLength; i++) {
            for (int j = i + 1; j < numLength; j++) {
                int distant = Math.abs(nums[i] - nums[j]);
                max = max > distant ? max : distant;
                Integer value = container.get(distant);
                if (value == null) {
                    if (total < gap) {
                        total++;
                        container.put(distant, 1);
                    } else {
                        if (distant < max) {
                            total++;
                            container.put(distant, 1);
                        }
                    }
                } else {
                    container.put(distant, value + 1);
                }
            }
        }
        List<Integer> list = container.keySet().stream().sorted().collect(Collectors.toList());
        int size = list.size();
        int result = 0;
        for (int i = 0; i < size; i++) {
            Integer key = list.get(i);
            Integer value = container.get(key);
            sum += value;
            if (sum >= k) {
                result = key;
                break;
            }
        }
        return result;
    }

}
